/**
 * 剑指 Offer 51. 数组中的逆序对
 * https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 */

// /**
//  * @param {number[]} nums
//  * @return {number}
//  */
// function reversePairs(nums) {
//   if (!nums.length) {
//     return 0;
//   }
//   const queue = [];
//   let count = 0;
//   for (let i = 0; i < nums.length; i += 1) {
//     let j = 0;
//     for (; j < queue.length; j += 1) {
//       if (nums[queue[j]] <= nums[i]) {
//         break;
//       }
//       if (queue[j] < i) {
//         count += 1;
//       }
//     }
//     queue.splice(j, 0, i);
//   }
//   return count;
// }

let count = 0;

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function mergeSort(nums) {
  if (nums.length === 1) {
    return nums;
  }
  const middle = Math.floor(nums.length / 2);
  const sub1 = mergeSort(nums.slice(0, middle));
  const sub2 = mergeSort(nums.slice(middle));
  const result = new Array(nums.length);
  let p1 = 0;
  let p2 = 0;
  let p = 0;
  while (p1 < sub1.length && p2 < sub2.length) {
    if (sub1[p1] > sub2[p2]) {
      result[p] = sub1[p1];
      p1 += 1;
    } else {
      result[p] = sub2[p2];
      p2 += 1;
      count += p1;
    }
    p += 1;
  }
  if (p1 < sub1.length) {
    while (p1 < sub1.length) {
      result[p] = sub1[p1];
      p1 += 1;
      p += 1;
    }
  }
  if (p2 < sub2.length) {
    while (p2 < sub2.length) {
      result[p] = sub2[p2];
      p2 += 1;
      count += p1;
      p += 1;
    }
  }
  return result;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
function reversePairs(nums) {
  if (!nums.length) {
    return 0;
  }
  count = 0;
  mergeSort(nums);
  return count;
}

console.log(reversePairs([7, 5, 6, 4]) === 5);
console.log(reversePairs([]) === 0);
console.log(reversePairs([5]) === 0);
console.log(reversePairs([1, 2, 3, 4, 5]) === 0);
console.log(reversePairs([233, 2000000001, 234, 2000000006, 235, 2000000003, 236, 2000000007, 237, 2000000002, 2000000005, 233, 233, 233, 233, 233, 2000000004]) === 69);
